"""
    二分查找算法的时间复杂度为0(logn)
"""
from run_time import *
@run_time
def twofen(li, val):
    left = 0  # 定义左范围
    right = len(li) - 1  # 定义右范围
    while left <= right:  # 当left大于right意味着左右范围已经查找完元素了
        mind = (left + right) // 2  # mind为left和right的中位数
        if li[mind] > val:
            right = mind - 1
        elif li[mind] < val:
            left = mind + 1
        else:
            return mind
    else:
        return None


@run_time
def chazhao(a, b):
    for x, y in enumerate(a):  # a的列表长度，所以这里的时间复杂度为:O(n)
        if y == b:
            return x
        else:
            return -1


@run_time
def cj():
    return list(range(10000))


if __name__ == '__main__':
    li = cj()
    chazhao(li, 38955)
    twofen(li, 38955)
